﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.dfs
{
    //79.单词搜索
    //给定一个二维网格和一个单词，找出该单词是否存在于网格中。
    //单词必须按照字母顺序，通过相邻的单元格内的字母构成，
    //其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
    public class _79
    {
        public bool Exist(char[][] board, string word)
        {
            int h = board.Length;
            int w = board[0].Length;
            Boolean[,] visited = new Boolean[h,w];
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    bool flag= check(board,visited,i,j,word,0);
                    if (flag)
                    {
                        return true;
                    }
                }
            }
            return false; 

        }
        public bool check(char[][] board, Boolean[,] visited, int i, int j, string s, int k)
        {
            if (board[i][j] != s[k])
            {
                return false;
            }
            else if (k == s.Length - 1)//已经够了满足所有条件
            {
                return true;
            }
            int[,] directions = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
            Boolean result = false;
            for (int q = 0; q < directions.Length; q++)
            {
                int newx=i+directions[q,0], newy = j + directions[q, 1];
                if (newx>=0&&newx<board.Length&&newy>=0&& newy<directions.GetLength(1))
                {
                    Boolean flag = check(board, visited, newx, newy, s, k + 1);
                    if (flag)
                    {
                        result = true;
                        break;
                    }
                }
            }
            visited[i, j] = false;
            return result;

        }
    }
}
